package leetcode.D100.T72;

class Solution {
    // 一刷
    // 递归解法
    /*private String word1;
    private String word2;
    public int minDistance(String word1, String word2) {
        this.word1 = word1;
        this.word2 = word2;
        return getDp(word1.length()-1, word2.length()-1);
    }
    private int getDp(int i, int j) {
        if(i == -1) return j + 1;
        if(j == -1) return i + 1;

        if(word1.charAt(i) == word2.charAt(j)) {
            return getDp(i-1, j-1);
        } else {
            return Math.min(Math.min(getDp(i, j-1)+1, getDp(i-1, j)+1), getDp(i-1, j-1)+1);
        }
    }*/

    // 动态规划解法（在递归基础上加入DP table进行优化，因为有重叠子问题）
    /*public int minDistance(String word1, String word2) {
        int m = word1.length(), n = word2.length();
        int[] dp = new int[n + 1];
        for(int j=0; j<=n; ++j) {
            dp[j] = j;
        }
        for(int i=1; i<=m; ++i) {
            int last = dp[0];
            dp[0] = i;
            for(int j=1; j<=n; ++j) {
                if(word1.charAt(i-1) == word2.charAt(j-1)) {
                    int temp = dp[j];
                    dp[j] = last;
                    last = temp;
                } else {
                    int temp = Math.min(dp[j-1]+1, last+1);
                    last = dp[j];
                    dp[j] = Math.min(temp, dp[j]+1);
                }
            }
        }
        return dp[n];
    }*/

    // 二刷
    /*public int minDistance(String word1, String word2) {
        int m = word1.length(), n = word2.length();
        int[] dp = new int[n+1];
        for(int i=0; i<n+1; ++i) {
            dp[i] = i;
        }
        for(int i=0; i<m; ++i) {
            int last = dp[0];
            dp[0] = i + 1;
            for(int j=1; j<n+1; ++j) {
                int min = Integer.min(dp[j-1], dp[j]) + 1;
                int temp = word1.charAt(i) == word2.charAt(j-1) ? last : last + 1;
                last = dp[j];
                dp[j] = Integer.min(min, temp);
            }
        }
        return dp[n];
    }*/

    // 三刷
    /*public int minDistance(String word1, String word2) {
        int[] dp = new int[word2.length()+1];
        for(int i=0; i<word2.length()+1; ++i) {
            dp[i] = i;
        }
        for(int i=0; i<word1.length(); ++i) {
            int last = dp[0];
            dp[0] = i+1;
            for(int j=1; j<word2.length()+1; ++j) {
                int temp = Math.min(dp[j-1], dp[j]);
                int result = word1.charAt(i) == word2.charAt(j-1) ? Math.min(temp+1, last) : Math.min(temp, last)+1;
                last = dp[j];
                dp[j] = result;
            }
        }
        return dp[dp.length-1];
    }*/

    // 四刷
    /*public int minDistance(String word1, String word2) {
        int m = word1.length(), n = word2.length();
        int[] dp = new int[n+1];
        for (int i=1; i<=n; ++i)
            dp[i] = i;
        for (int i=1; i<=m; ++i) {
            int last = dp[0];
            dp[0] = i;
            for (int j=1; j<=n; ++j) {
                int temp = Math.min(dp[j-1], dp[j]);
                int result = word1.charAt(i-1) == word2.charAt(j-1) ? Math.min(last, temp+1) : Math.min(last, temp) + 1;
                last = dp[j];
                dp[j] = result;
            }
        }
        return dp[n];
    }*/

    // 五刷
    public int minDistance(String word1, String word2) {
        int[] dp = new int[word2.length() + 1];
        for (int i=0; i<dp.length; ++i)
            dp[i] = i;
        for (int i=0; i<word1.length(); ++i) {
            int last = dp[0];
            dp[0] = i + 1;
            for (int j = 1; j < dp.length; ++j) {
                int temp = dp[j];
                if (word1.charAt(i) == word2.charAt(j-1)) {
                    dp[j] = last;
                } else {
                    dp[j] = Math.min(dp[j-1], Math.min(last, dp[j])) + 1;
                }
                last = temp;
            }
        }
        return dp[dp.length-1];
    }
}